package subject1.tiling;

import java.util.ArrayList;

/**
 * @Author CandyWall
 * @Date 2022/6/4--14:36
 * @Description 贴瓷砖
 */
public class Solution {
    // 获取网格上面的两个坐标间的顶点
    public ArrayList<int[]> getVertexes(int x1, int y1, int x2, int y2) {
        // 计算线段穿过的格子顶点坐标
        ArrayList<int[]> passbyPostions = new ArrayList<>();
        // 垂直
        if (x1 == x2) {
            int deltaY = y1 < y2 ? 1 : -1;
            for (int y = y1; y != y2; y += deltaY) {
                passbyPostions.add(new int[]{x2, y});
            }
            passbyPostions.add(new int[]{x2, y2});
        }
        // 水平
        else if (y1 == y2) {
            int deltaX = x1 < x2 ? 1 : -1;
            for (int x = 0; x != x2; x += deltaX) {
                passbyPostions.add(new int[]{x, y2});
            }
            passbyPostions.add(new int[]{x2, y2});
        }
        // 45度或者135度斜着
        else {
            int deltaX = x1 < x2 ? 1 : -1;
            int deltaY = y1 < y2 ? 1 : -1;
            for (int x = x1, y = y1; x != x2 && y != y2 ; x += deltaX, y += deltaY) {
                passbyPostions.add(new int[]{x, y});
            }
            passbyPostions.add(new int[]{x2, y2});
        }

        return passbyPostions;
    }

    // 判断线段是否在瓷砖内
    public boolean lineInTiles(ArrayList<int[]> passbyPostions, int[][] positions) {
        // 线段上面每两个顶点找一个左上角的点看看是否在瓷砖列表里面
        for (int i = 1; i < passbyPostions.size(); i++) {
            int[] p1 = passbyPostions.get(i - 1);
            int[] p2 = passbyPostions.get(i);
            int x = Math.min(p1[0], p2[0]);
            int y = Math.min(p1[1], p2[1]);
            boolean contains = false;
            for (int[] position : positions) {
                if (x == position[0] && y == position[1]) {
                    contains = true;
                }
            }
            if (!contains) {
                return false;
            }
        }
        return true;
    }

    public int tiling(int rows, int cols, int[][] lines, int[][] positions) {
        int count = 0;
        // 遍历所有的线段
        for (int i = 0; i < lines.length; i++) {
            // 线段的两个端点
            // 获取线段穿过的格子顶点坐标
            ArrayList<int[]> passbyPostions = getVertexes(lines[i][0], lines[i][1], lines[i][2], lines[i][3]);
            /*for (int[] passbyPostion : passbyPostions) {
                System.out.print("(" + passbyPostion[0] + ", " + passbyPostion[1] + ") -> ");
            }
            System.out.println();*/
            if (lineInTiles(passbyPostions, positions)) {
                count++;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[][] lines1 = {{1, 1, 2, 2}, {2, 1, 0, 3}};
        int[][] positions1 = {{0, 1}, {1, 1}, {2, 2}};
        System.out.println(new Solution().tiling(3, 4, lines1, positions1));

        int[][] lines2 = {{3, 5, 0, 2}, {0, 3, 2, 3}, {4, 2, 6, 4}, {3, 1, 6, 4}, {5, 3, 7, 5}};
        int[][] positions2 = {{0, 1}, {2, 4}, {1, 3}, {3, 3}, {4, 2}, {5, 5}, {5, 3}, {6, 4}};
        System.out.println(new Solution().tiling(7, 6, lines2, positions2));
    }
}
